Public-key signature methods are described in publications by Diffie and Hellmann (W. Diffie, M. E. Hellmann, “New Directions in Cryptography”, IEEE Transactions on Information Theory, vol. IT-22, November 1976, pages 644-654) and by Rivest, Shamir and Adleman (R. Rivest, A. Shamir and L. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”, Communications of the ACM, vol. 27, no. 2, February 1978, pages 120-126, RSA methods). These conventional methods utilize two keys, one of which is used for signing a message and another for verifying this signature. A secret key known only to the sender of the message is used for signing, while a public key is used for verifying the signature. Such public-key signature methods are used predominantly in data communications via electronic media, the digital signature being used as a substitute for a hand-written signature. The public key enables the recipient of the message to verify the authenticity of the signature and, thus, of the document transmitted to him or her. Examples of applications of the aforementioned signature methods have been described in detail in A. Beutelspacher, “Kryptologie”, (Cryptology) Vieweg-Verlag 1994.
German Patent application No. 195 13 896 describes a public-key signature method which uses a polynomial, whose coefficients are formed from the message to be signed and from a random number. From the thus formed polynomial, two further polynomials are derived, which must include at least one zero in a finite field, because these are used to form the signature. If this is not the case, the described method must be repeated with a different random number.
Schwenk J. et al.: “Public Key Encryption and Signature Schemes Based on Polynomials over Zn Advances in Cryptology-Eurocrypt, 1996 International Conference on the, Theory and Application of Cryptographic Techniques, Saragossa, May 12-16, 1996, May 12, 1996, Maurer U. (ed), pages 60-71, describes a method for generating a digital signature of a message, this being accomplished by a secret key comprising at least two large prime numbers and the digital signature being the zero value of a polynomial P(x)−m modulo n. General polynomials f(x) are used as polynomials. Although the zero value is discovered when the digital signature is decrypted, it has become evident in the case of general polynomials f(x) that this zero value is not unique, i.e. the digital signature cannot be uniquely generated.
Varadharajan, V.: “Cryptosystem Based on Permutation Polynomials” International Journal of Computer Mathematics, 1988, London, vol. 23, no. 3-4, pages 235-250, describes a use of permutation polynomials for encrypting a message. A disadvantage, however, is that only those permutation polynomials can be used for which there is an inverse function.
Therefore, an object of the present invention is to provide a signature method for signing a message, where the method avoids the mentioned disadvantage, exhibits a level of security and speed of execution comparable to the existing methods, and, in this context, permits a valid signature to be generated at all times.
Signature methods which use polynomials over the ring of numbers modulo of a number n made up of at least two large prime numbers are already known from the publications described above. Other examples are those methods which are based on so-called Dickson polynomials (W. B. Müller, R. Nöbauer, Cryptanalysis of the Dickson scheme. Proc. Eurocrypt 8S, Lecture Notes in Computer Science, vol, 219, 1986, pages 50-61). The present invention goes beyond the teachings of the mentioned papers to the extent that the method for generating a signature is substantially more general in nature and makes it possible to employ other classes of polynomials as well.